package jTree;

import graph.Graph;
import graph.graphNode;

import java.util.*;

import queries.mapAssign;

public class JunctionTree {

	public long numberOfNodes; 
	public ArrayList<NodeSet> treeNodes = null;
	
	
	public JunctionTree(){
		
	}
	public JunctionTree(Graph g){
		//System.out.println("Finding Maximal Cliques of the Graph!!!");
		//System.out.println("Using Maximam Cardinality Search");
	
		ArrayList<Node> order = new ArrayList<Node>();
		
		cardinalitySearch(order,g);	//performing Cardinality search
		
		
		treeNodes = new ArrayList<NodeSet>();
		for(int i = order.size() - 1; i>=0; i--){
			
			if(i!=order.size()-1 && order.get(i).neighbourCount < order.get(i+1).neighbourCount){
				continue;
			}
			
			// Found a new clique
			
			long count = order.get(i).neighbourCount; 	// keeping count of the clique size 
			NodeSet clique = new NodeSet();
			clique.list.add(order.get(i));
			for(int j = i-1; j>=0 && count>0; j--){
				if(g.isEdge( order.get(i).index, order.get(j).index)){
					count--;
					clique.list.add(order.get(j));
				}
			}
			
			treeNodes.add(clique);		// adding the new found clique
		}
	
		/*
		System.out.println("The cliques found are");
		
		for(int j = 0; j<treeNodes.size(); j++){
			
			System.out.print("Clique "+j+":\t");
			for(Node n : treeNodes.get(j).list){
				System.out.print(n.index+"  ");
			}
			System.out.println();
		} 
		*/
	
		// Creating a graph between the cliques and then forming the spanning tree
		createSpanningTree(treeNodes);
		
		createPotentialTable(treeNodes);
		
	
		
		
	
	}
		
	@Override
	public String toString() {
		return "JunctionTree [numberOfNodes=" + numberOfNodes + ", treeNodes="
				+ treeNodes + "]";
	}
	/*public void cardinalitySearch(ArrayList<Node> order,Graph g){
		order.add(new Node(0));			// initial element added with count zero
				
		Comparator<Node> comparator = new NodeComparator();
		PriorityQueue<Node> pqueue = new PriorityQueue<Node>(100,comparator);
		for(int i = 1; i<g.numNodes; i++){
			pqueue.add(new Node(i));			// Adding Nodes in priority queue
		}
		
		while(!pqueue.isEmpty()){
			
			for (Node node : pqueue) {
				if(g.isEdge( order.get( order.size()-1 ).index, node.index )){
					node.neighbourCount++;												// For every node in pqueue havong
				}																        // an edge with the last node removed their
			}																			// count is increased by 1.
			
			order.add(pqueue.remove());
		}
	
		System.out.println("Neighbour Count of the nodes in triangulated graph by Cardinality Serach");
		
		System.out.println("NodeIndex   NeighbourCount   Order");
		for(Node node : order){
			System.out.println(node.index +"   "+node.neighbourCount+"   "+order.indexOf(node));
		} 
	}*/

	public void cardinalitySearch(ArrayList<Node> order,Graph g){
		order.add(new Node(0));			// initial element added with count zero

		ArrayList<Node> dummy = new ArrayList<Node>();

		for(int i = 1; i<g.numNodes; i++){
			dummy.add(new Node(i));
		}

		while(!dummy.isEmpty()){

			for (Node node : dummy) {
				if(g.isEdge( order.get( order.size()-1 ).index, node.index )){
					node.neighbourCount++;												// For every node in pqueue havong
				}																        // an edge with the last node removed their
			}																			// count is increased by 1.

			int nodeMax = -1;
			long numMaxNode = -1;

			for(int i=0;i<dummy.size();i++){
					if(dummy.get(i).neighbourCount > numMaxNode ){
						nodeMax = i;
						numMaxNode =  dummy.get(i).neighbourCount;
					}
			}


			order.add(dummy.get(nodeMax));
			dummy.remove(nodeMax);
		}
		
		/*
		System.out.println("Neighbour Count of the nodes in triangulated graph by Cardinality Serach");

		System.out.println("NodeIndex   NeighbourCount   Order");
		for(Node node : order){
			System.out.println(node.index +"   "+node.neighbourCount+"   "+order.indexOf(node));
		}
		*/
	}
		
	public void createSpanningTree(ArrayList<NodeSet> tree){
		
		int cliqueGraph[][] = new int[100][100];
		
		for(int i = 0; i<tree.size()-1; i++){
			for(int j = i+1; j<tree.size(); j++){
				ArrayList<Node> intersection = new ArrayList<Node>(tree.get(i).list);
				intersection.retainAll(tree.get(j).list);
				
				if(intersection.size() > 0){
					cliqueGraph[i][j] = intersection.size();
					cliqueGraph[j][i] = intersection.size();
				}
				else{
					cliqueGraph[i][j] = 1000;         			// Assigning a very large value assumed to be infinity
					cliqueGraph[j][i] = 1000;
				}	
			}
		}
		
		Comparator<Edge> comparator = new EdgeComparator(); 
		PriorityQueue<Edge> pq = new PriorityQueue<Edge>(1000,comparator);
		
		Set<Integer> visited = new HashSet<Integer>();
		visited.add(0);			// adding initial clique node
		
		int lastVisited = 0;
		
	//	System.out.println("Inside Max Spanning Tree generating code");
		
		while(visited.size() != tree.size()){
			
			for(int i = 0; i<tree.size(); i++)
			{
				if(i != lastVisited && cliqueGraph[lastVisited][i] != 1000 ){					// if edge does not have infinite weight and is not self loop 
					if(!visited.contains(i)){
						Edge e = new Edge(lastVisited, i, cliqueGraph[lastVisited][i]);			// and does not contain both vertices as visited.
						pq.add(e);																// adding edge to priority queue
						//System.out.println("Edge added to queue :("+e.source+","+e.destination+") with weight "+e.weight);
					}
				}
			}
		
			Edge t;
			while(true){
			
				t = pq.remove();
				if(visited.contains(t.destination) && visited.contains(t.source) )
					continue;
				else
					break;
			}			
			
			//System.out.println("Edge removed :("+t.source+","+t.destination+") with weight "+t.weight);
			
			lastVisited = t.destination;
			visited.add(lastVisited);
				
			tree.get(t.source).branch.add(t.destination);
			tree.get(t.destination).branch.add(t.source);
		
		}

		/*
		for(NodeSet m: tree){ 
			
			System.out.print("clique "+tree.indexOf(m)+" is connected to ");
			for(int n: m.branch){
				System.out.print(n+" ");
			}
			System.out.println();
		} 
		*/
	
	}	

	public void createPotentialTable(ArrayList<NodeSet> tree){
		
		for(NodeSet clq: treeNodes){
		
			List<Node> s = new ArrayList<Node>(clq.list);
			clq.offset = new int[s.size()];                   // stores the offset in the table for every element in the table.
			
			clq.offset[s.size() -1] = 1;
			for(int i = s.size()-2; i>=0; i--){
				clq.offset[i] = clq.offset[i+1] * (int)Graph.maxValues[(int)s.get(i+1).index];
			}
		
			clq.table = new mapAssign[clq.offset[0] * (int)Graph.maxValues[(int)s.get(0).index]];
			for(int i = 0; i<clq.offset[0] * (int)Graph.maxValues[(int)s.get(0).index]; i++){
				clq.table[i] = new mapAssign();
				clq.table[i].value = 1;
				
			}
						
		}		
		
		for(graphNode n: Graph.ListOfPotentials){
			
			List<Integer> t1;
			List<Integer> t2;
			
			for(NodeSet clq : treeNodes){
			
				t1 = new ArrayList<Integer>(n.nodesPresent);
				t2 = new ArrayList<Integer>();
				
				for(Node x : clq.list){
					t2.add((int)x.index);
				}
			
				t1.removeAll(t2);
			
				if(!t1.isEmpty())
					continue;
			
			//	System.out.println("Potential "+Graph.ListOfPotentials.indexOf(n)+" is assigned to "+treeNodes.indexOf(clq));
				
			//	System.out.println("Size of nodesPresent in potential "+n.nodesPresent.size());
				
				Integer variableValues[] = new Integer[n.nodesPresent.size()]; 
			
				for(int i = 0; i<clq.table.length; i++){
						
						//System.out.println("Assigning Table value for "+i);	
						for(int j = 0; j<clq.list.size(); j++){
						
							int index = n.nodesPresent.indexOf((int)clq.list.get(j).index);
							
							if(index >= 0){
								variableValues[index] = ( i / clq.offset[j] ) % (int)(Graph.maxValues[(int)clq.list.get(j).index]);
								//System.out.print(variableValues[index]+ " ");
							}	
						}
						//System.out.println();
						//System.out.println();
						List<Integer> qr =  Arrays.asList(variableValues);
						clq.table[i].value = clq.table[i].value * n.values.get(qr);
				}
			
				break;
			}
		
		}
	
	
	/*	for(NodeSet clq: treeNodes){
			System.out.println("Table for Clique "+treeNodes.indexOf(clq));
			
			for(int i = 0; i<clq.table.length; i++){
				System.out.println(i+" "+clq.table[i].value);
			}
		} */
	
	
	
	}	

} 

class NodeComparator implements Comparator<Node>{

	@Override
	public int compare(Node arg0, Node arg1) {
		// TODO Auto-generated method stub
		if( arg0.neighbourCount > arg1.neighbourCount ){
			return -1;
		}
		
		return 1;
	}
	
}

class EdgeComparator implements Comparator<Edge>{

	@Override
	public int compare(Edge arg0, Edge arg1) {
		// TODO Auto-generated method stub
		if( arg0.weight > arg1.weight ){
			return -1;
		}
		
		return 1;
	}
	
}
